1. Field of the Invention
The present invention relates to an overlay network system in which at least one node is assigned in a hash space by distributed hash table techniques, and to a service providing method used in the overlay network system.
2. Description of the Related Art
Recently, as an alternative to client/server systems, an increasing interest is being paid to a form of connection called peer to peer (hereinafter referred to as P2P), in which all the nodes connected to a network can dynamically change their roles. In contrast to a client/server system, in which data is concentrated at a server, in a P2P system, data is saved in peer nodes in a distributed manner. That is, searching for a location where data is saved is performed by cooperation among the peer nodes.
An example of techniques for searching for a location where data is saved is a distributed hash table (hereinafter referred to as DHT). In DHT, information indicating a location where a body of data is saved is registered at a node having a hash value that is approximate to a hash value generated from the data. At this time, the same hash function is used to generate the hash value of the data and the hash value of the node. At each node where information indicating a location where data is saved is registered, pairs of a hash value of the data and the information indicating the location where the body of the data is saved are maintained in the form of a hash table.
Since hash values generated from different data take on entirely different values, nodes at which information indicating locations where data is saved are distributed on the network. That is, hash tables are stored in the peer nodes in a distributed manner, so that the load is distributed among the peer nodes.
When searching for data is performed, the data can be found by calculating a hash value of the data and performing searching using the hash value as a key. In DHT, every node constituting the network has a routing table describing routes to neighboring nodes. In the routing table, the distance between nodes is represented using hash values of the nodes.
In order to refer to data registered at one of the nodes on the network, first, a hash value of the data is calculated, and a searching request is issued to a node having a value that is closest to the hash value of the data with reference to the routing table in the own node. If the node that has received the searching request does not have information indicating a location where the data is saved, the node that has received the searching request issues a searching request to a node having a hash value that is most approximate to the hash value of the data with reference to the routing table in the own node. By repeating this operation, the range of searching becomes narrower, and information indicating the location where the data is saved can be found in the end. When information indicating the location where the data is saved has been obtained, it is possible to obtain the data body on the basis of the information. That is, in an overlay network constructed using DHT techniques, it is possible to access a data body without considering the location of the data body.
As described, above, in DHT, routing is performed on the basis of distances between peer nodes, represented using hash values. Thus, it is not needed to be aware of segments provided on an IP network. That is, it is possible to construct an overlay network using DHT in which routing is performed in a layer above the IP layer.
Services provided on an overlay network can be broadly classified into two types, namely, local services provided by individual nodes and global services relating to the overlay network as a whole. Examples of local services provided by individual nodes include a Web service and an FTP service. The services provided by the individual nodes are available only during periods in which the nodes are alive on the network, and the services become unavailable when the nodes have left the network.
In contrast, even when, for example, a node has newly joined the overlay network or a node has left the overlay network, global services are expected to be available as long as the overlay network exists. Examples of global services include an authentication service that is used when a new node joins the overlay network, and a node list service and a service list service for management.
When global services are provided, some measures are often taken in order to improve the availability of the global services, for example, a server for providing global services is provided on the network, or some nodes are designated in advance as super nodes that act like servers. The scheme in which a server is provided on an overlay network is called hybrid P2P, and the scheme in which super nodes are provided on an overlay network is called super-node hybrid P2P. On the other hand, the scheme in which an overlay network is purely formed of peer nodes alone is called pure P2P.
Japanese Unexamined Patent Application Publication No. 2005-196676 discloses a hybrid P2P system in which a central server is provided in addition to peer nodes.